package com.contain2.selfmap.demo2;

import java.util.AbstractMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

import com.contain2.abstractcontain.demo1.Countries;
import com.contain2.selfmap.demo1.MapEntry;

/**
 * 经过散列优化
 * 
 * @author Administrator
 *
 */
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {

	// 选择一个质数作为散列表的尺寸大小
	static final int SIZE = 997;

	// 表示实际散列表的数组，为了能够自动处理冲突，使用了LinkedList数组，每个新元素只是直接添加到list末尾的某个特定的桶位中。
	LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];

	public V put(K key, V value) {
		V oldValue = null;
		// 为了使产生的数字适合buckets数组的大小，取模操作符将按照该数组的尺寸取模。
		int index = Math.abs(key.hashCode()) % SIZE;

		if (buckets[index] == null) {
			// 如果是null，则表示还没有元素被散列至此，所以为了保存刚散列到该定位的对象，需要创建一个新的LinkedList
			buckets[index] = new LinkedList<MapEntry<K, V>>();
		}

		LinkedList<MapEntry<K, V>> bucket = buckets[index];
		MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
		boolean found = false;
		ListIterator<MapEntry<K, V>> it = bucket.listIterator();

		while (it.hasNext()) {
			MapEntry<K, V> iPair = it.next();
			if (iPair.getKey().equals(key)) {
				// 如果有元素，将旧值赋给oldValue，用新值取代旧值，found表示是否找到旧值，如果没有，则将新值的对添加到list末尾
				oldValue = iPair.getValue();
				it.set(pair);
				found = true;
				break;
			}
		}

		if (!found) {
			buckets[index].add(pair);
		}
		return oldValue;
	}

	public V get(Object key) {
		int index = Math.abs(key.hashCode()) % SIZE;
		if (buckets[index] == null) {
			return null;
		}
		for (MapEntry<K, V> iPair : buckets[index]) {
			if (iPair.getKey().equals(key)) {
				return iPair.getValue();
			}
		}
		return null;
	}

	@Override
	public Set<java.util.Map.Entry<K, V>> entrySet() {
		Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
		for (LinkedList<MapEntry<K, V>> bucket : buckets) {
			if (bucket == null) {
				continue;
			}
			for (MapEntry<K, V> mPair : bucket) {
				set.add(mPair);
			}
		}
		return set;
	}

	public static void main(String[] args) {
		SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
		for (String[] sarr : Countries.DATA) {
			m.put(sarr[0], sarr[1]);
		}
		System.out.println(m);
		System.out.println(m.get("ALGERIA"));
		System.out.println(m.entrySet());
	}

}
